LuCloud 6 Q & A Array & ArrayBuffer

LuCloud 6 Q & A Array & ArrayBuffer

五月 27, 2019

cover

Array

Array/数组是Scala最基本的数据结构之一，它是可变的mutable、可索引的indexed数据集合。

Array[T]是Java的T[]的“Scala”表示形式。尽管一方面，Scala数组与Java数组一一对应。也就是说，Scala数组Array [Int]是Java int []的一种表示形式、Array [Double]是Java double []的一种表示形式、Array [String]是Java String []的一种表示形式。但与此同时，Scala Array提供的功能远远超过Java的相应的Array：

  • 首先，Scala数组可以是通用的generic。也就是说，你可以有一个Array [T]，其中T是一个类型参数或抽象类型。
  • 其次，Scala数组与Scala序列兼容compatible——您可以传递需要Seq [T]的Array [T]。
  • 最后，Scala数组还支持所有序列操作。

generic

Scala的Array [T]这样的通用数组在运行时可以是Java的任意八个基本数组类型byte []，short []，char []，int []，long []，float []，double []，boolean []，或者是一个对象数组。包含所有这些类型的唯一常见运行时类型是AnyRef（或等效的java.lang.Object），因此这是Scala编译器映射Array [T]的类型。

在运行时，当访问或更新Array [T]类型的数组元素时，会有一系列类型测试确定实际的数组类型，然后在Java数组上执行正确的数组操作。这些类型测试稍微减慢了数组操作。您可以期望对通用数组的访问比对原始数组或对象数组的访问慢三到四倍。这意味着如果你需要最大的性能，你应该更喜欢具体而不是通用数组。表示一种通用的数组类型是有所不足的，但是，却必须有一种方法来创建通用数组。

Scala同Java一样，不能创建泛型数组，因为在运行时会擦除数据类型。

这里涉及到了泛型数组，由于我是Java小白，等看完Java Core再解释吧。

Java为了成功创建泛型数组要做的工作比较复杂，而Scala由于泛型数组使用的比较广泛，因此这里提供了一些运行时提示帮助编译器知道运行时实际类型参数：

  • ClassTag：此运行时提示采用scala.reflect.ClassTag类型的类清单class manifest的形式。类清单是一个类型描述符对象，它描述了类型的顶级类。使用ClassTag的代码如下：

    1
    2
    3
    4
    5
    scala> def wrap(xs: Vector[U])(implicit m: ClassTag[T]) = evenElems(xs)
    wrap: [U](xs: Vector[U])(implicit evidence$1: scala.reflect.ClassTag[U])Array[U]
    // the line above is equivalent to
    scala> def wrap[U: ClassTag](xs: Vector[U]) = evenElems(xs)
    wrap: [U](xs: Vector[U])(implicit evidence$1: scala.reflect.ClassTag[U])Array[U]

  • Mainfest上下文界定：除了类清单之外，还有类型为scala.reflect.Manifest的完整清单，它描述了类型的所有方面。但是对于数组创建，只需要类清单，因此具体内容略。

compatible

在Scala2.8之前的版本中，Scala编译器在名为boxing和unboxing的过程中的需要时，魔幻般地将数据wrapped到Seq对象并从Seq对象中unwrapped出来。

Previously, the Scala compiler somewhat “magically” wrapped and unwrapped arrays to and from Seq objects when required in a process called boxing and unboxing. The details of this were quite complicated, in particular when one created a new array of generic type Array[T]. There were some puzzling corner cases and the performance of array operations was not all that predictable.

在Scala2.8及之后的版本中，采用了更加聪明的方法——去除了编译器的魔法，转而用对隐式转换implicit conversions的系统性使用作为替代。这里主要有到WrappedArray和到ArrayOps的两种隐式转换：

WrappedArray

1
2
3
4
5
abstract class WrappedArray[T]
extends AbstractSeq[T]
    with IndexedSeq[T]							// 是Seq的子类
    with ArrayLike[T, WrappedArray[T]]
    with CustomParallelizable[T, ParArray[T]]

scala.collection.mutable.WrappedArray是IndexedSeq的子类，Array会隐式地转换为此类型，而非伪装成Seq，因为本地的Array的数据类型表示不是Seq的子类。

在伴随对象object WrappedArray的实现中，直接使用array完成每个转换函数，以ofByte类为例，其实现了Array到WrappedArray的转换：

1
2
3
4
5
6
7
8
9
10
11
final class ofByte(val array: Array[Byte]) extends WrappedArray[Byte] with Serializable {
    def elemTag = ClassTag.Byte
    def length: Int = array.length
    def apply(index: Int): Byte = array(index)
    def update(index: Int, elem: Byte) { array(index) = elem }
    override def hashCode = MurmurHash3.wrappedBytesHash(array)
    override def equals(that: Any) = that match {
        case that: ofByte => Arrays.equals(array, that.array)
        case _ => super.equals(that)
    }
}

ArrayOps

1
2
3
4
sealed trait ArrayOps[T] 
extends Any
    with ArrayLike[T, Array[T]] 
    with CustomParallelizable[T, ParArray[T]]

不同于Seq的子类WrappedArray，ArrayOps只是将所有序列方法“添加”到数组，但不会将数组本身转换为序列。 通常，此ArrayOps对象是短暂的；在调用序列方法后，它通常是不可访问的，并且它的存储可以被回收。现代VM通常完全避免创建此对象。

不同于WrappedArray，ArrayOps的伴随对象以WrappedArray为基础，以ofByte类为例，其实现了Array到WrappedArray的转换：

1
2
3
4
5
6
7
8
9
10
11
/** A subclass of `ArrayOps` for arrays containing `Byte`s. */
final class ofByte(override val repr: Array[Byte]) extends AnyVal with ArrayOps[Byte] with ArrayLike[Byte, Array[Byte]] {

    override protected[this] def thisCollection: WrappedArray[Byte] = new WrappedArray.ofByte(repr)
    override protected[this] def toCollection(repr: Array[Byte]): WrappedArray[Byte] = new WrappedArray.ofByte(repr)
    override protected[this] def newBuilder = new ArrayBuilder.ofByte

    def length: Int = repr.length
    def apply(index: Int): Byte = repr(index)
    def update(index: Int, elem: Byte) { repr(index) = elem }
}

ArrayOps和WrappedArray之间的一个显著区别在于：在使用诸如converse、filter、map等操作时，ArrayOps会生成/yeild一个Array，而WrappedArray会保留其WrappedArray类型。

The difference between ArrayOps and WrappedArray is that calling transformer methods such as filter and map will yield an array, whereas a WrappedArray will remain a WrappedArray.

Implicit Conversion

在执行一些Seq的相关操作时，Array被自动转换为ArrayOps或WrappedArray，其实质在Seq的操作函数执行之前插入到转换类型的类型转换函数，例如下列代码：

1
2
3
4
5
scala> a1.reverse
res1: Array[Int] = Array(3, 2, 1)
// the line above is equivalent to
scala> intArrayOps(a1).reverse
res2: Array[Int] = Array(3, 2, 1)

priority

上例中编译器首先选择对intArrayOps的转换而非对WrappedArray的其他隐式转换，这是因为ArrayOps转换的优先级高于WrappedArray转换。

可能在较早的Scala版本（8年前的代码版本）中，第一个是在Predef对象中定义的，而第二个是在类scala.LowPriorityImplicits中定义的，它由Predef继承。子类和子对象中的Implicits优先于基类中的implicits。因此，如果两个转换都适用，则选择Predef中的转换。

在最新的Github代码版本中，并未找到传说中的scala.LowPriorityImplicits类，而这两个隐式转换都写在了Predef中，其优先级可能是由代码顺序决定的。

ArrayBuffer

Concept

ArrayBuffer是Buffer类、GenericTraversableTemplate类、ResizableArray类和Serializable等类的一种实现，使用Array在内部表示汇编序列。

1
2
3
4
5
6
7
8
9
class ArrayBuffer[A](override protected val initialSize: Int) extends AbstractBuffer[A]
    with Buffer[A]
    with GenericTraversableTemplate[A, ArrayBuffer]
    with BufferLike[A, ArrayBuffer[A]]
    with IndexedSeqOptimized[A, ArrayBuffer[A]]
    with Builder[A, ArrayBuffer[A]]
    with ResizableArray[A]
    with CustomParallelizable[A, ParArray[A]]
    with Serializable

ArrayBuffer的本质是Array，对它的操作实质上是访问和修改其底层Array，因此ArrayBuffer上的大多数操作都具有与Array相同的速度。append、update和随机访问需要常量时间（摊销时间），而prepend和remove是线性的。

Principle

ArrayBuffer内部缓冲区维护一个Array和size（代码中为size0）。运行原理以append操作为例（代码如下）：

  • 将元素添加append到ArrayBuffer时，首先将检查size：

    • 如果底层Array未满，则将元素直接添加到Array中；
    • 如果底层Array已满，则构造一个更大的Array，并将所有元素复制到新数组。新数组的构建方法如下代码所示：
    1
    2
    3
    4
    5
    6
    private def ensureSize(size: Int) {
        if (capacity < size || capacity == 0) {
            var newsize = if (capacity == 0) 16 else capacity * 2
            while (newsize < size) newsize *= 2
            resize(newsize)
        }

  • 添加元素到Array末尾：将Array的size位赋为添加的元素；

  • size++.

1
2
3
4
5
6
7
8
9
10
11
12
/** Appends a single element to this buffer and returns
 *  the identity of the buffer. It takes constant amortized time.
 *
 *  @param elem  the element to append.
 *  @return      the updated buffer.
 */
def +=(elem: A): this.type = {
  ensureSize(size0 + 1)
  array(size0) = elem.asInstanceOf[AnyRef]
  size0 += 1
  this
}

Features

  • 连续性：ArrayBuffer的实质是Array，而Array（Scala）的实质是Java的T[]，由于Java数组占用内存上的连续空间，因此ArrayBuffer在内存上具有连续性；
  • 可变性Mutable：ArrayBuffer和Array都属于可变的数据集合，可以修改某一索引对应的元素值；
  • 长度可变性Resizable：Array长度固定，而ArrayBuffer长度可变，可添加删除元素；
  • 可序列化Serializable。

Why we use this

在Spark源码中，CacheManager的实现中使用到了ArrayBuffer，其主要利用了ArrayBuffer的Resizable特点，可以通过维护一个ArrayBuffer，不断向此buffer添加元素，达到一定长度再提交，从而实现缓冲功能。

Difference

  • 长度可变性Resizable：
    • Array长度固定，在声明长度后可以进行元素的更新，不能进行改变长度的元素添加和删除操作；
    • ArrayBuffer长度可变，提供了一系列如append、prepend、remove等改变长度的元素操作。
  • 实现差异：
    • Array在JVM级别实现，是Java的T[]的“Scala”表示形式。通过一些隐式转换将Array与Seq结合，提供比Java数组更多的功能；
    • ArrayBuffer通过在内部维护一个Array来实现，并在需要时分配一个新的Array。
  • 效率差异：Array专门用于内置值类型（Unit除外），因此Array [Int]将比ArrayBuffer [Int]更优化——Array值不必被boxed，因此使用更少的内存和更少的间接化。

Source